Relational databases are used for storage and retrieval of information. The information is structured in the database as two-dimensional tables of rows and columns. A column heading designates the type of data stored in each column. The information is stored in a non-volatile medium such as a disk array.
Users may access the database information typically by using database management software. The database storage media and management software together comprise a database management system, or DBMS. DBMSs may be implemented on a centralized mainframe system, or may be distributed in a client-server network, as examples.
The database management software includes specialized commands for accessing the database information. For example, a common command for accessing data is a Structured Query Language (SQL) xe2x80x9cselectxe2x80x9d query. Using the select query, one or more rows from one or more tables of the database may be retrieved.
Traditionally, DBMSs processed queries in batch mode. In other words, a user wanting to extract information from the database would submit a query, wait a long time during which no feedback is provided, and then receive a precise answer.
Today, on-line aggregation and adaptive query processing present alternatives to traditional batch query processing. On-line aggregation permits progressively refined running aggregates of a query to be continuously displayed to the requesting user. The running aggregates, or intermediate results, are displayed typically along with a xe2x80x9cconfidencexe2x80x9d factor. Adaptive query processing involves an iterative feedback process in which the DBMS receives information from its environment and uses the information to adapt the behavior of the query.
One area of optimization involves join operations. When queries involving multiple tables are made, a join operation may be performed. Upon receiving the multi-table query, tuples, or rows, from one table are joined with tuples from a second table, to produce a result. An equijoin is a type of join operation in which an entry, or column, of a tuple from one table has the same value as an entry of a tuple from a second table.
A band join is a non-equijoin of tuples of two tables in which the join condition is a range or band rather than an equality. Band joins may be useful in queries that involve real world domains, such as time, position, or price.
For example, suppose that a user of the DBMS wants to investigate the correlation between the situation of the stock market and important company events. Two tables, PRICE and NEWS, are involved. Tuples of PRICE represent the oscillation of stocks within a day, with attribute PRICE.C representing the time of the measurement in seconds. Tuples of NEWS represent financial news articles events, with attribute NEWS.D representing the time in seconds that the article was released.
Suppose the user wants to find all pairs of events occurring at nearly the same time, such that the first event represents a great oscillation of a stock within a day, and the second event represents a news event that mentions the company. Such a query may use a band join. The query may be written in SQL as:
SELECT PRICE.SYMBOL, NEWS.ARTICLE, PRICE.PERCENT_CHANGE
FROM PRICE, NEWS
WHERE PRICE.PERCENT_CHANGE greater than 10
AND PRICE.C-NEWS.D less than =300
AND PRICE.C-NEWS.D greater than =xe2x88x92300
AND NEWS.ARTICLE.CONTAINS (PRICE.SYMBOL)
One of the conditions uses a join operation, in which the difference between attribute, PRICE.C, and attribute, NEWS.D, is itself between xe2x88x92300 and 300. Tuples that meet the join criteria become part of the result table for the query.
There are two kinds of widely used traditional band join algorithms: the partitioned band join algorithm, which employs both a partitioning phase and a sorting phase, and the sort-merge band join algorithm, which employs a sorting phase and several merging phases. Both of these band join algorithms generate no results before the final phase. Thus, these types of band join algorithms are xe2x80x9cblocking,xe2x80x9d and, thus, are inappropriate for on-line aggregation and adaptive query processing. If, instead, users of the DBMS receive an approximation of the final results during processing, the query may, in some cases, be aborted, long before its completion.
In accordance with the embodiments described herein, a method and apparatus are disclosed in which first tuples are stored in a first table in a database system, second tuples are stored in a second table in the database system, the first and second tuples are partitioned into plural portions, and the first and second tuples are joined based upon the partitioning portions.
In other embodiments, the selection of any first tuple to be joined with any second tuple is random. In still other embodiments, result tuples are available after performing only a single join operation.
Other features and embodiments will become apparent from the following description, from the drawings, and from the claims.